# -*- coding:utf-8 -*-
# @File       :   x的平方根.py
# @Author     :   LINING
# @Time       :   2024/3/5 15:49
# @Description :  整数二分
"""
https://leetcode.cn/problems/sqrtx/description/
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
输入：x = 4
输出：2
解法，最后一个nxn小于x的数
"""


def get_num(target):
    left = 1
    right = target
    while left < right:
        mid = int((left+right+1)/2)
        if mid * mid > target:
            right = mid-1
        else:
            left = mid
    return right


print(get_num(4))

